package com.lfg.leetcode.leetcode200;

import java.util.ArrayList;
import java.util.List;

public class No282addOperators {


    public static void main(String[] args) {
        List<String> ret = addOperators("105", 5);
        System.out.println(ret);
    }

    public static List<String> addOperators(String num, int target) {
        List<String> ret = new ArrayList<>();
        dfs(num, 0, 0, 0, "", ret, target);
        return ret;
    }


    public static void dfs(String num, long total, long preTotal, int index, String path, List<String> ret, int target) {
        int length = num.length();
        if (index >= length) {
            if (total == target) {
                ret.add(path);
            }
            return;
        }
        for (int i = index + 1; i <= length; i++) {
            String substring = num.substring(index, i);
            if (substring.length() > 1 && substring.charAt(0) == '0') {
                continue;
            }
            long value = Long.valueOf(substring);
            if (index == 0) {
                dfs(num, value, value, i, substring, ret, target);
                continue;
            }
            dfs(num, total + value, value, i, path + "+" + substring, ret, target);
            dfs(num, total - value, -value, i, path + "-" + substring, ret, target);
            dfs(num, total - preTotal + preTotal * value, preTotal * value, i, path + "*" + substring, ret, target);
        }
    }


}
